package com.colin.leetcode;

import org.junit.Assert;
import org.junit.Test;

public class S0004_Median_Of_Two_Sorted_Arrays {

    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            // 确保nums1是较短的数组，优化二分查找效率
            if (nums1.length > nums2.length) {
                int[] temp = nums1;
                nums1 = nums2;
                nums2 = temp;
            }

            int m = nums1.length;
            int n = nums2.length;
            int left = 0, right = m;

            // 总长度的奇偶性判断
            boolean isEven = (m + n) % 2 == 0;
            int totalLeft = (m + n + 1) / 2; // 向上取整，保证左半部分至少有一个元素

            while (left <= right) {
                int i = left + (right - left) / 2; // nums1的分割点
                int j = totalLeft - i; // nums2的分割点

                // 处理边界情况和比较条件
                int nums1Left = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
                int nums1Right = (i == m) ? Integer.MAX_VALUE : nums1[i];
                int nums2Left = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
                int nums2Right = (j == n) ? Integer.MAX_VALUE : nums2[j];

                // 找到正确的分割点
                if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
                    if (isEven) {
                        return (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2.0;
                    } else {
                        return Math.max(nums1Left, nums2Left);
                    }
                } else if (nums1Left > nums2Right) {
                    right = i - 1;
                } else {
                    left = i + 1;
                }
            }

            throw new IllegalArgumentException("Input arrays are not sorted");
        }
    }

    @Test
    public void test() {
        Solution solution = new Solution();
        Assert.assertEquals(4.5, solution.findMedianSortedArrays(new int[]{1, 2, 3, 4}, new int[]{5, 6, 7, 8}), 0.001);
        Assert.assertEquals(3.0, solution.findMedianSortedArrays(new int[]{1, 2, 3, 4, 5}, new int[]{1, 2, 3, 4, 5}), 0.001);
        Assert.assertEquals(2.5, solution.findMedianSortedArrays(new int[]{1, 99}, new int[]{2, 3}), 0.001);
        Assert.assertEquals(2.0, solution.findMedianSortedArrays(new int[]{1, 3}, new int[]{2}), 0.001);
        Assert.assertEquals(4.0, solution.findMedianSortedArrays(new int[]{1, 3, 5, 7}, new int[]{2, 4, 6}), 0.001);
        Assert.assertEquals(3.0, solution.findMedianSortedArrays(new int[]{1, 5, 99}, new int[]{2, 3}), 0.001);
    }
}